package org.example.SolutionNew001;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DoublePoint03 {
    public static void main(String[] args) {
        DoublePoint03 dp = new DoublePoint03();
        int[] nums = new int[]{-1, 0, 1, 2, -1, -4};
        System.out.println(dp.threeSum(nums));
    }

    //遗憾立场
    public List<List<Integer>> threeSum0(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = n; i > 0; i--) {
            for (int j = 0; j < i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < n - 2; i++) {
            for (int start = i + 1; start < n - 1; start++) {
                int flag = -(nums[i] + nums[start]);
                for (int end = start + 1; end < n; end++) {
                    if (nums[end] == flag) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[start]);
                        list.add(nums[end]);
                        res.add(list);
                        break;
                    }
                }
                while (nums[start + 1] == nums[start] && start < n - 2) {
                    start++;
                }
            }
            while (nums[i] == nums[i + 1] && i < n - 3) {
                i++;
            }
        }
        return res;
    }

    //官解思路
    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for (int first = 0; first < n; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) continue;
            int third = n - 1;
            int target = -nums[first];
            for (int second = first + 1; second < n; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) continue;
                while (third > second && nums[third] + nums[second] > target) third--;
                if (third == second) break;
                if (nums[third] + nums[second] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    res.add(list);
                }
            }
        }
        return res;
    }

    //评论区大佬思路
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int first = 0; first < n; first++) {
            if (nums[first] > 0) break;
            if (first > 0 && nums[first] == nums[first - 1]) continue;
            int start = first + 1, end = n - 1;
            int target = -nums[first];
            while (start < end) {
                int sum = nums[start] + nums[end];
                if (sum == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[start]);
                    list.add(nums[end]);
                    res.add(list);
                    start++;end--;
                    while(end>start&&nums[start]==nums[start-1]) start++;
                    while(end>start&&nums[end]==nums[end+1]) end--;
                }else if(sum>target){
                    end--;
                    while(end>start&&nums[end]==nums[end+1]) end--;
                }else{
                    start++;
                    while(end>start&&nums[start]==nums[start-1]) start++;
                }
            }
        }
        return res;
    }
}
